package cn.xaut.二叉树;

import cn.xaut.剑指offer.m20.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 222. 完全二叉树的节点个数
 */
public class demo222 {

    // 递归解法
    public int countNodes(TreeNode root) {

        // 递归终止条件
        if (root == null)
            return 0;
        
        // 递归过程
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

    // 非递归解法
    public int countNodes2(TreeNode root) {
        
        if (root == null)
            return 0;
        
        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            res ++;
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
        return res;
    }
}
